package main.Q1501_1600;

import java.util.*;

public class Q1591_1600 {
    public static void main(String[] args) {
        System.out.println("Question1591：");
        System.out.println("Question1592：");
        System.out.println("Question1593：");
        System.out.println("Question1594：");
        System.out.println("Question1595：");
        System.out.println("Question1596：");
        System.out.println("Question1597：");
        System.out.println("Question1598：");
        System.out.println("Question1599：");
        System.out.println("Question1600：位继承顺序");
    }
}

class Question1600 {
    Map<String, List<String>> edges;
    Set<String> dead;
    String king;

    public Question1600(String kingName) {
        edges = new HashMap<String, List<String>>();
        dead = new HashSet<String>();
        king = kingName;
    }

    public void birth(String parentName, String childName) {
        List<String> children = edges.getOrDefault(parentName, new ArrayList<String>());
        children.add(childName);
        edges.put(parentName, children);
    }

    public void death(String name) {
        dead.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> result = new ArrayList<String>();
        preorder(result, king);
        return result;
    }

    public void preorder(List<String> result, String name) {
        if (!dead.contains(name)) {
            result.add(name);
        }
        List<String> children = edges.getOrDefault(name, new ArrayList<String>());
        for (String childName : children) {
            preorder(result, childName);
        }
    }
}